package day4;


import java.util.List;
import java.util.PriorityQueue;

public class ch4 {

    public class ListNode {
     int val;
     ListNode next;
     ListNode() {}
     ListNode(int val) { this.val = val; }
     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 }

     //148
     public ListNode sortList(ListNode head) {

        return divide(head,null);

     }

     public ListNode divide(ListNode begin,ListNode end){
         if (begin == null) {
             return begin;
         }

        if(begin.next==end){
            return begin;
        }
        ListNode slow = begin,fast = slow;
        while (fast.next!=null&&fast.next.next!=null){
            slow = slow.next;
            fast = fast.next.next;
        }
        ListNode mid = fast.next;
        fast.next = null;

        ListNode left = divide(begin,null);
        ListNode right = divide(mid,end);
        ListNode result = merge(left,right);

        return result;


     }


     public ListNode merge(ListNode left,ListNode right){
        ListNode pr = new ListNode(0);
        ListNode f = pr;
        while (left!=null&&right!=null){
            if(left.val<right.val){
                ListNode next = left.next;
                left.next = null;
                f.next = left;
                left = next;
            }else {
                ListNode next = right.next;
                right.next = null;
                f.next = right;
                right = next;
            }
            f = f.next;
        }

        if(left==null) f.next=right;
        if(right==null) f.next=left;

        return pr.next;


     }


    //23
    public ListNode mergeKLists(ListNode[] lists) {
        ListNode head = new ListNode();
        ListNode f = head;
        PriorityQueue<ListNode> queue = new PriorityQueue<>((a,b)->a.val-b.val);
        for (ListNode l:lists){
            if(l!=null){
                queue.offer(l);
            }
        }
        while (!queue.isEmpty()){
            ListNode p = queue.poll();
            if(p.next!=null){
                queue.offer(p.next);
            }
            f.next = p;
            p.next = null;
            f = f.next;
        }


        return head.next;



    }



}
